A. Field of the Invention
The present invention relates to computer graphic systems that are used for computer aided geometric design, and more particularly, to methods of using a computer graphic system for changing a geometric model that is bounded by free-form surfaces.
B. The Prior Art
With the advent of computers computer aided design (CAD) became a subject of widespread interest. Increasingly, computer keyboards, cursors, CRT's and graphics terminals are replacing pencil and paper, and computer disks and tapes are replacing drawing vaults.
A. A. G. Requicha and H. B. Voelcker have provided a useful survey of the historical development and contemporary assessment of CAD systems. See, "Solid Modeling: A Historical Summary and Contemporary Assessment," IEEE Computer Graphics and Applications, Vol. 2 No. 2, March 1982, pp. 9-24 (hereinafter Solid Modeling I); see also, "Solid Modeling: Current Status and Research Directions," IEEE Computer Graphics and Applications, Oct. 1983, pp. 25-37 (in which the same authors provide an update to their 1982 article, hereinafter referred to as Solid Modeling II).
As noted by the above-named authors in Solid Modeling I, after the advent in the 1950's and 1960's of interactive computer graphic systems, computerized homogeneous coordinate (projective) geometry for manipulating graphic designs and NC programming languages, CAD systems generally began to develop in four areas. One of the earliest of these four areas was the development of what is known as "wireframes." In the wireframe graphic system, internal geometric data, which initially consisted of simple lists of lines and arcs, could be scanned by application programs and used to plot drawings and photomasks and to produce point-to-point NC code for drilling and punching. Later on, the two-dimensional lines and arcs of such wireframe systems were replaced with three-dimensional space curves which could be projected computationally to produce multiple orthographic, isometric and perspective views. Basically, the wireframe system was and is a collection of lines and curved segments representing an object's edges.
As further noted in Solid Modeling I, while clearly useful, the three-dimensional wireframe systems of today exhibit serious deficiencies. Models produced using a wireframe system may be ambiguous, that is to say, the object may represent any one of several possible objects defined by the same set of edges. Another deficiency is that wireframe systems tolerate or permit "nonsense objects" to be produced, such as objects where an edge is missing and which therefore do not correspond to any real life possibility. Another deficiency is that objects with curved surfaces which are attempted using wireframe systems result in profile lines or silhouettes that are viewpoint-dependent artifacts rather than physical edges. And fourth, such systems require a large amount of low level data to describe an object that may be relatively simple.
A second type of CAD system which has been developed and refined since the 1960's are those which use polygonal schemes. In this type of system graphic rendering is the primary object of the system. CAD systems which rely on such polygonal schemes must typically address what the authors in Solid Modeling I term the "visibility problem." In essence, these systems address the problem of how one can determine computationally and represent graphically those portions of an object that are visible from a specified viewpoint. Such systems typically solve the visibility problem by representing objects with polyhedra having hundreds or thousands of polygonal faces (or facets) and by using algorithms which perform smoothing and spacial sorting operations that typically involve face and edge comparisons and determination of hidden lines and surfaces.
A third major area of CAD system development in those systems which may be used to generate and manipulate sculptured surfaces. The emphasis in this area has been on the accurate representation of surfaces, and on the tailoring of such representations to meet various functional and aesthetic criteria. However, as the authors in Solid Modeling I note, surprisingly little attention has been paid to computer methods for possessing sculptured surfaces: namely, displaying and efficiently computing curves of intersection, testing closedness (e.g., to determine whether a surface may qualify as a boundary of a solid), etc.
In short, while nonetheless useful, CAD systems which employ polygonal schemes or sculptured surfaces, like wireframes, suffer from some significant disadvantages, particularly in that such systems are informationally incomplete.
A fourth area of CAD system development, called solid modeling, is directed to systems and methods focused on informationally complete representations of solids, or in other words representations that permit in principle any well defined geometrical property of any represented object to be calculated automatically. Solid modeling CAD systems have to date been based on principally three types of systems: boundary representation systems, constructive solid geometry systems, and sweep-based systems, or various hybrid combinations of these three systems.
FIG. 1A represents a typical boundary representation (B-rep) system. In this type of system the boundary surfaces of the model are individually represented, as illustrated at 20-28. The B-rep scheme defines a solid model such as that generally indicated at 29 in FIG. 1B by keeping account of the boundary surfaces 20-28, edges, and vertices along with adjacency information.
Constructive solid geometry (CSG) systems typically rely on the use of Boolean logic (union (AND), difference (NOT) and intersection (EXCLUSIVE OR)) to combine basic solid shapes (called primitives). As shown in FIG. 2A, by adding the primitives illustrated at 30 and 32 and then subtracting the primitive 31 from the result, the solid model generally indicated at 33 in FIG. 2B (which consists of a solid L-shaped object with a hole 34) can be produced, similar to the model 29 produced using the B-rep scheme illustrated in FIG. 1A.
A third prior art approach which is known is the use of sweep-based systems. In these systems, as generally illustrated in FIG. 3A, by translating the plane 35 in a vertical direction the portion 37 (see FIG. 3B) of the model can be generated, whereas by vertically translating the plane 36 having the hole in the middle of it, portion 38 of the object can be formed. Thus, by adding the shapes generated from sweeping planes 35 and 36 the complete model 39 is produced.
Most of the research recently directed toward development of solid geometric modeling systems has taken the approach of incorporating existing free-form surface modeling systems (e.g., sculptured surface techniques) into the standard type of solid modeling systems such as B-rep, CSG and sweep-based systems. However, this forced marriage has caused other problems. For example, one such problem arises in computing the curve of intersection of two free-form surface patches. It can be shown, for example, that such a curve cannot, in general, be expressed precisely using parametric equations. Indeed, for two bicubic patches, the curve of intersection is generally degree 324. In contrast, two quadric surfaces intersect in a curve of degree 4, which can be expressed exactly using parametric equations.
Another significant problem resulting from this forced marriage arises in representing the topology of a free-form surface patch which has been intersected with a second patch. For example, a bicubic patch has four sides, but after intersection it may have three sides, five or more sides, or even a hole in the middle.
For these and other reasons, solid geometric modeling systems have been slow to use surfaces which are more complex than quadrics. What has long been overlooked is that a fresh approach to the problem of solid free-form geometric modeling might avoid many of the problems which have arisen from attempting to marry the present free-form surface modeling systems to current solid modeling technology. Indeed, as noted by Requicha and Voelcker in Solid Modeling II, as recently as 1983, notwithstanding a proliferation of activity in the area of solid modeling systems, the basic approach has remained the same. See, for example, the systems represented in Table I at page 26 of Solid Modeling II.
Thus, what is needed in the art is a computer graphics method for modeling solid objects which addresses and substantially overcomes many of the problems and limitations which presently exist under state of the art technology. Indeed, as noted by the authors in Solid Modeling I, development of more powerful solid geometric modeling CAD systems "will remove a major roadblock to flexible automation and permit the single `A` in CAD/CAM to represent `Automated` rather than `Assisted.`"